package com.kehao.leetcode.hard.array;

import org.junit.Test;

import java.util.HashMap;

public class MinWindowSolution {
    public String minWindow(String s, String t) {
        StringBuffer sb = new StringBuffer(s);
        String result = null;
        HashMap<Character,Integer> tMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if(tMap.containsKey(c)){
                tMap.put(c,tMap.get(c)+1);
            }else {
                tMap.put(c,1);
            }
        }
        int pos = 0;
        for (int i = 0; i < sb.length(); i++) {
            if(tMap.containsKey(sb.charAt(i))){
                pos = i;
                break;
            }
        }
        sb.delete(0,pos);
        for (int i = sb.length()-1; i>=0 ; i--) {
            if(tMap.containsKey(sb.charAt(i))){
                pos = i;
                break;
            }
        }
        sb.delete(pos+1,sb.length());

        HashMap<Character,Integer> sMap = new HashMap<>();
        int l=0; int r=0;
        int minLen = Integer.MAX_VALUE ;
        while (r<=sb.length()){
            while (r<=sb.length()&&!condition(tMap,sMap)){
                r = moveRightPos(sMap,sb,r,1);
            }
            while (l<r&&condition(tMap,sMap)){
                l = moveLeftPos(sMap,sb,l,1);
            }
            l = moveLeftPos(sMap,sb,l,-1);
            if(l<0) return "";
            if(minLen>r-l){
                minLen = r-l;
                result = sb.substring(l,r);
            }
            r = moveRightPos(sMap,sb,r,1);
            l = moveLeftPos(sMap,sb,l,1);
        }
        return result;

    }
    public boolean condition(HashMap<Character,Integer> tMap, HashMap<Character,Integer> sMap){
        boolean result = true;
        for(char c:tMap.keySet()){
            if(!(sMap.containsKey(c)&&sMap.get(c)>=tMap.get(c))){
                result = false;
                break;
            }
        }
        return result;
    }

    public int moveLeftPos(HashMap<Character,Integer> sMap,StringBuffer sb,int l,int direction){
        if(direction==1){
            char c = sb.charAt(l);
            sMap.put(c,sMap.get(c)-1);
            l++;
        }else if(direction ==-1){
            l--;
            if(l>=0){
                char c = sb.charAt(l);
                sMap.put(c,sMap.get(c)+1);
            }
        }
        return l;
    }
    public int moveRightPos(HashMap<Character,Integer> sMap,StringBuffer sb,int r,int direction){
        if(direction==1){
            if(r<sb.length()){
                char c = sb.charAt(r);
                if (sMap.containsKey(c)) sMap.put(c,sMap.get(c)+1);
                else sMap.put(c,1);
            }
            r++;
        }else if(direction ==-1){
            r--;
            char c = sb.charAt(r);
            sMap.put(c,sMap.get(c)-1);
        }
        return r;
    }

    @Test
    public void test(){
        String s = "XXXXXABCXXXXXXXX";
        String t = "ABC";
        String result = minWindow(s,t);
        System.out.println(result);
    }

    @Test
    public void test01(){
        String s = "ADOBECODEBANC";
        String t = "ABC";//输出："BANC"
        String result = minWindow(s,t);
        System.out.println(result);
    }

    @Test
    public void test02(){
        String s = "a";
        String t = "a";//输出："a"
        String result = minWindow(s,t);
        System.out.println(result);
    }

    @Test
    public void test03(){
        String s = "a";
        String t = "aa";//输出：""
        String result = minWindow(s,t);
        System.out.println(result);
    }
}
